// 可以多次交易，每次交易都有手续费
// 主要区别在于递推公式

// 1. 第i天持有股票
//     1. 第i天保持持有，`dp[i - 1][0]`
//     2. 第i天买入股票, `dp[i-1][1] - prices[i]`
//     3. `dp[i][0] = Math.max(dp[i - 1][0], dp[i-1][1] - prices[i])`
// 2. 第i天不持有股票
//     1. 第i天保持不持有，`dp[i-1][1]`
//     2. 第i天卖出，`dp[i-1][0]+ prices[i] -free`
//     3. `dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0]+ prices[i] -fee)`

// 思路1， 卖出的时候计算手续费
function maxProfit(prices, fee) {
    let dp = new Array(prices.length).fill(0).map(_ => [0, 0])
    dp[0][0] = -prices[0]
    for (let i = 1; i < prices.length; i++) {
        dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i])
        dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i] - fee)
    }
    return dp[prices.length-1][1]
}

// 思路2，买入的时候计算手续费
function maxProfit2(prices, fee) {
    let dp = new Array(prices.length).fill(0).map(_ => [0, 0])
    dp[0][0] = -prices[0] -fee
    for (let i = 1; i < prices.length; i++) {
        dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i] - fee)
        dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i])        
    } 
    return dp[prices.length - 1][1]
}

let  prices = [1, 3, 2, 8, 4, 9], fee = 2
console.log(maxProfit(prices, fee))
console.log(maxProfit2(prices, fee))